/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class CBTInserter {
    /**
    我们可以使用一个队列存储这些可以添加子节点的节点。队列中的存储顺序为：首先「从左往右」存储倒数第二层最右侧的节点，再「从左往右」存储最后一层的全部节点。这一步可以使用广度优先搜索来完成，因为广度优先搜索就是按照层优先进行遍历的。

随后，当我们每次调用 insert(val) 时，我们就创建出一个节点 child，并将它最为队列的队首节点的子节点。在这之后，我们需要把 child 加入队尾，并且如果对队首节点已经有两个子节点，我们需要将其从队列中移除。
     */

    Queue<TreeNode> childdata;
    TreeNode root;

    public CBTInserter(TreeNode root) {
        this.childdata = new ArrayDeque<>();
        this.root = root;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);//该root有可能不止一个节点，他是一个树

        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();//遍历每一个节点，并且弹出
            if(node.left != null) {//判断该节点，左右是否存在，存在放在queue中，时每一个节点都遍历
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
            if(!(node.left != null && node.right != null)) {//判断该节点左右是否存在，一旦有一方没有，放在childdata队列中
                childdata.offer(node);
            }
        }
    }
    
    public int insert(int v) {
        TreeNode child = new TreeNode(v);
        TreeNode node = childdata.peek();
        int ret = node.val;
        if (node.left == null) {
            node.left = child;
        } else {
            node.right = child;
            childdata.poll();
        }
        childdata.offer(child);
        return ret;
    }
    
    public TreeNode get_root() {
        return root;
    }
}

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter obj = new CBTInserter(root);
 * int param_1 = obj.insert(v);
 * TreeNode param_2 = obj.get_root();
 */